package leetcode_day._2021._202104._1120;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/11 21:38
 * 丑数 II
 * 给你一个整数 n ，请你找出并返回第 n 个 丑数
 * 1 通常被视为丑数
 * 思路：
 *  动态规划
 *  设置三个指针，p2 p3 p5，p2 指针表示该指针当前指向的数能够 × 2
 *  三个指针开始都指向第一个数
 *  指针移动的条件：如果指针乘上当前指向的数是最小的，那么这个指针就向后移动
 */
public class _11_264 extends Object {
    public static void main(String[] args) {
        System.out.println(new _11_264().nthUglyNumber(10));
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(1);
        list.add(2);
        HashSet<Object> hashSet = new HashSet<>(list);
        System.out.println(new ArrayList<>(hashSet));
    }

    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            int num2 = 2 * dp[p2], num3 = 3 * dp[p3], num5 = 5 * dp[p5];
            dp[i] = Math.min(num2, Math.min(num3, num5));
            // 不能使用 if else , 因为有可能有两个都等于
            if (num2 == dp[i]) ++p2;
            if (num3 == dp[i]) ++p3;
            if (num5 == dp[i]) ++p5;
        }
        return dp[n];
    }
}
